Với a, b là hai số nguyên (a ≥ b), ta thực hiện chia a cho b được thương q, số dư r (r ≥ 0) tức là a = bq + r, khi đó ta có

UCLN ( a , b ) = { b n e ^ ´ u r = 0 UCLN ( b , r ) n e ^ ´ u r ≠ 0 {\displaystyle {\mbox{UCLN}}(a,b)={\begin{cases}{\begin{matrix}b&{\mbox{n}}{\acute {\hat {\mbox{e}}}}{\mbox{u}}&r=0\\{\mbox{UCLN}}(b,r)&{\mbox{n}}{\acute {\hat {\mbox{e}}}}{\mbox{u}}&r\neq 0\end{matrix}}\end{cases}}}

Trong đó r = a mod b